package leetcodehot100;

import java.util.HashMap;

/**
 * JZ48最长不含重复字符的子字符串
 */
public class _3无重复字符的最长子串 {
    /*
    给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     */
    //滑动窗口+哈希表
    public int lengthOfLongestSubstring (String s) {
        // write code here
        //哈希表记录窗口内非重复的字符
        HashMap<Character, Integer> mp = new HashMap<>();
        int res = 0;
        //设置窗口左右边界
        for(int left=0,right = 0; right<s.length();right++){
            //窗口右移进入哈希表统计出现次数
            if(mp.containsKey(s.charAt(right)))
                mp.put(s.charAt(right),mp.get(s.charAt(right))+1);
            else
                mp.put(s.charAt(right),1);

            //出现次数大于1，则窗口内有重复
            while (mp.get(s.charAt(right))>1)
                //窗口左移，同时减去该字符的出现次数
                mp.put(s.charAt(left),mp.get(s.charAt(left++))-1);
            //维护字串最大长度
            res = Math.max(res, right - left + 1);
        }
        return  res;
    }


    //动态规划+哈希表
    public int lengthOfLongestSubstring2 (String s) {
        //哈希表记录窗口内非重复的字符及其下标
        HashMap<Character, Integer> mp = new HashMap<>();
        int res = 0;
        //dp[i]表示以下标i结尾的字符串最长不含重复子串的长度
        int[] dp = new int[s.length() + 1];
        for(int i = 1; i <= s.length(); i++){
            dp[i] = 1;
            //哈希表中没有，说明不重复
            if(!mp.containsKey(s.charAt(i - 1)))
                //前一个加1
                dp[i] = dp[i - 1] + 1;
                //遇到重复字符
            else
                dp[i] = Math.min(dp[i - 1] + 1, i - mp.get(s.charAt(i - 1)));
            //加入哈希表
            mp.put(s.charAt(i - 1), i);
            //维护最大值
            res = Math.max(res, dp[i]);
        }
        return  res;
    }
}
